#!/usr/bin/python
# -*- coding: utf8 -*-
import traceback

class Cell(object):
	def __init__(self, value = None):
		self.value = value
		self.candidates = [True] * 9

	def set(self, value, silent = False):
		if self.value == value:
			return False
		elif self.value:
			raise RuntimeError("Invalid value set")
		self.value = value
		self.puzzle.update_candidates(self)
		if not silent:
			print "set value", value, self

	def accepts(self, value):
		if self.value == value:
			return True
		elif self.value:
			return False
		return self.candidates[value - 1]

	def clear(self, value, silent = False):
		if not self.value and self.candidates[value - 1]:
			self.candidates[value - 1] = False
			if not silent:
				print "clear candidate", value, self
			return True
		return False

	def match_singleton(self):
		if not self.value and self.candidates.count(True) == 1:
			return self.candidates.index(True) + 1
		return False

	def __repr__(self):
		id = "cell<%d,%d,%d " % (self.row, self.column, self.block)

		if self.value:
			value = str(self.value)
		else:
			value = "|".join(filter(None, map(lambda x, y: x and str(y) or "", self.candidates, range(1, 10))))
		return id + value + ">"
class Block(object):
	TYPES = [
		'row',
		'column',
		'block'
	]
	RESOLUTION_METHODS = [
		'match_singleton',
		'match_single_candidates',
		'clear_block_candidates'
	]
	def __init__(self, puzzle, type, index):
		self.puzzle = puzzle
		self.type = type
		self.index = index
		self.cells = []
	def __repr__(self):
		return "<%s:%d>" % (self.type, self.index)

	def add_cell(self, cell):
		self.cells.append(cell)
		setattr(cell, self.type, self.index)

	def update_candidates(self, silent = False):
		values = []
		for cell in self.cells:
			if cell.value:
				values.append(cell.value)
		for value in values:
			for cell in self.cells:
				cell.clear(value, silent)

	def cleared(self):
		for cell in self.cells:
			if not cell.value:
				return False
		return True

	def match_singleton(self):
		for cell in self.cells:
			value = cell.match_singleton()
			if value:
				cell.set(value)
				return True
		return False

	def match_single_candidates(self):
		for value in range(1, 10):
			candidates = []
			for cell in self.cells:
				if cell.accepts(value):
					candidates.append(cell)
			if len(candidates) == 1 and candidates[0].value != value:
				candidates[0].set(value)
				return True
		return False

	def clear_block_candidates(self):
		"""
		Remove candidates from other blocks if we can.

		If all candidates for a value are on the same
		/other type/ block. The all cells on this /other type/ block can
		not have candidates for this value on other block of my type.
		"""
		found = False
		other_types = ['row', 'column', 'block']
		other_types.remove(self.type)
		candidates = range(1, 10)
		for cell in self.cells:
			if cell.value:
				candidates.remove(cell.value)
		for other_type in other_types:
			for candidate in candidates:
				indexes = {}
				for cell in self.cells:
					if cell.accepts(candidate):
						indexes[getattr(cell, other_type)] = True
				indexes = indexes.keys()
				if len(indexes) == 1:
					# we have our match
					other_block = self.puzzle.get_block(other_type, indexes[0])
					#~ print "clear_block_candidates", candidate, other_type, indexes[0], self, other_block, self.puzzle
					for cell in other_block.cells:
						if getattr(cell, self.type) != self.index:
							# remove candidate
							if cell.clear(candidate):
								found = True
		return found


class Puzzle(object):
	def __init__(self, input = None):
		self.cells = []
		self.rows = []
		self.columns = []
		self.blocks = []
		self.elements = []
		for i in range(9):
			self.rows.append(Block(self, 'row', i))
			self.columns.append(Block(self, 'column', i))
			self.blocks.append(Block(self, 'block', i))
			assert self.blocks[i].index == i
		self.elements.extend(self.rows)
		self.elements.extend(self.columns)
		self.elements.extend(self.blocks)
		for i in range(9):
			for j in range(9):
				self.add_cell(Cell(), i, j)
		if input:
			self.read(input)

	def update_candidates(self, cell):
		for type in Block.TYPES:
			for c in self.get_block(type, getattr(cell, type)).cells:
				c.clear(cell.value, True)

	def add_cell(self, cell, row, column):
		block = (row / 3) * 3 + (column / 3)
		cell.puzzle = self
		self.cells.append(cell)
		self.rows[row].add_cell(cell)
		self.columns[column].add_cell(cell)
		self.blocks[block].add_cell(cell)
		assert cell.row == row
		assert cell.column == column
		assert cell.block == block

	def get_block(self, type, index):
		if type == 'row':
			return self.rows[index]
		elif type == 'column':
			return self.columns[index]
		elif type == 'block':
			return self.blocks[index]
		else:
			raise RuntimeError, "invalid block type requested"

	def cleared(self):
		for row in self.rows:
			if not row.cleared():
				return False
		return True

	def update_blocks_candidates(self, silent = False):
		for element in self.elements:
			element.update_candidates(silent)

	def apply_block_method(self, method):
		for element in self.elements:
			if getattr(element, method)():
				return True
		return False

	def resolve(self, silent = False):
		while True:
			modified = False
			for method in Block.RESOLUTION_METHODS:
				self.update_blocks_candidates(True)
				if self.apply_block_method(method):
					modified = True
					if not silent:
						print "resolution method succeeded", method
					break

			if self.cleared():
				return True
			if not modified:
				return False

	def read(self, input):
		row = 0
		for line in input.split('\n'):
			column = 0
			for char in line:
				if char != ' ':
					value = int(char)
					self.rows[row].cells[column].set(value, True)
				column += 1
			row += 1

	def __str__(self):
		lines = []
		for row in self.rows:
			values = []
			for cell in row.cells:
				values.append(str(cell.value or ' '))
			lines.append("".join(values))
		return "\n".join(lines)

	def unresolved(self):
		for cell in self.cells:
			if not cell.value:
				print cell

TEST = """
 3   9165
   6 5 89
2
    8  93
 6  17
7    6 18
8   9 7
  1 2"""

TEST2 = """
     3 85
  1 2
   5 7
  4   1
 9
5      73
  2 1
    4   9"""

TEST3 = """  2 9 1 7
 386
4
     5
  9 1 3
   4
        4
     792
8 6 3 7
"""

TEST4 = """        3
4    1 8
1  95
8  7 6 54
 3     7
   51
5 7    3
       61
  94  5
"""

p = Puzzle(TEST4)


try:
	resolved = p.resolve()
except:
	traceback.print_exc()
	resolved = False

if not resolved:
	p.unresolved()

print p
